

#include <string.h>
#include <stdio.h>
#include "huffman.h"

typedef struct RegArvHuf *ArvHuf;

typedef struct RegArvHuf {
  int peso;                      /* peso da �rvore */
  char letra;                    /* somente no caso de folha */
  short int filho;               /* indica a rela��o com o pai:
                                    0: esq, 1: dir */
  ArvHuf esq,dir,pai;            /* sub�rvores e pai */
} RegArvHuf;

ArvHuf Arvore;   /*  As fun��es abaixo construir�o e utilizar�o a
		     �rvore que ser� apontada por esta vari�vel */


ArvHuf Folhas[TamanhoMaxAlfabeto];   /* Apontadores para as folhas da
					�rvore 'Arvore', com Folhas[0]
					correspondendo � letra 'a',
					Folhas[1] � letra 'b', etc */

/* --------------------------------------------------------- */
/* Fun��es auxiliares para este m�dulo                       */
/* --------------------------------------------------------- */

ArvHuf CriaFolha(char letra, int peso) {
/* Cria uma folha da �rvore; devolve NULL se n�o h� mais mem�ria. */

	ArvHuf A = malloc(sizeof(RegArvHuf));
	
	if (A==NULL) return NULL;  /* Retorna NULL se n�o h� mais mem�ria*/
	else
	{
		A->peso = peso;    /*Substitui os valores na nova*/
		A->letra = letra;  /*folha criada                */
		A->dir = NULL;
		A->esq = NULL;
		
		return A;          /*Retorna a nova folha com todos os dados*/
	}

} /* CriaFolha */

ArvHuf CombinaArvs(ArvHuf esq, ArvHuf dir) {
/* Combina duas sub�rvores numa �nica �rvore cujo peso � a soma dos
   pesos das sub�rvores; devolve NULL se n�o h� mais mem�ria. */
  
	ArvHuf A = malloc(sizeof(RegArvHuf));
	
	if (A==NULL) return NULL;       /* Retorna NULL se n�o h� mais mem�ria*/
	else
	{
		A->peso = (esq->peso + dir->peso); /*O peso � a soma dos pesos das subarvores*/
		A->dir = dir;			   /*Atualiza os ponteiros*/
		A->esq = esq;
		
		esq->filho = 0;		/*O campo filho indica se o n� � filho esquerdo (0), ou*/
		dir->filho = 1;		/*direito (1) do seu pai.			       */
		
		esq->pai = A;		/*As duas subarvores combinadas possuem o mesmo pai*/
		dir->pai = A;
		
		return A;		/*Retorna a arvore combinada*/
	}
   
   
} /* CombinaArvs */

void DesceHeap(ArvHuf fl[], int n) {
/* Desce o elemento da raiz fl[0] para dentro da fila de prioridade de
   'n' elementos */
  
     /*Algoritmo baseado na apostila*/
     
     int k, m=0;
     ArvHuf x;
     Boolean continua = true;
     
     x = fl[0];
     k = 1;
     
     while ((continua) && (k<n))
     {
          if (k<n-1)
          {
                if (fl[k]->peso > fl[k+1]->peso)  k = k+1;
          }
          
          if (x->peso > fl[k]->peso)
          {
                fl[m] = fl[k];
                m = k;
                k = 2*k+1;
          }
          else continua = false;
     }
          fl[m] = x;
	
  
 } /* DesceHeap */
  
void SobeHeap(ArvHuf fl[], int m) {
/* Sobe o �ltimo elemento fl[m] para dentro da fila de prioridade */
  
    /*Algoritmo baseado na Apostila*/
    
    int j;
    ArvHuf x;
    
    x = fl[m];
    j = (m-1)/2;
    
    while ((m>0) && (fl[j]->peso > x->peso))
    {
        fl[m]=fl[j];
        m = j;
        j = (j-1)/2;
    }
    fl[m] = x;
 
} /* SobeHeap */

void ConstroiHeap(ArvHuf fl[], int n) {
/* Transforma o vetor 'fl' de 'n' elementos numa fila de
   prioridades, com peso m�nimo na raiz */
   
   /*Algoritmo baseado na apostila*/
  	
     int m;
     
     for (m=1; m<n; m++) SobeHeap(fl, m);
 
} /* ConstroiHeap */

ArvHuf Minimo(ArvHuf fl[], int *n) {
/* Devolve o elemento m�nimo da fila de prioridade fl' (raiz) e o
   elimina da estrutura; acerta o valor de 'n'. */

   ArvHuf x = fl[0]; /*Guarda em x o menor elemento, q fica na primeira posi��o*/
   
   fl[0] = fl[(*n)-1];  /*Copia o ultimo elemento para a primeira posi��o para desce-lo e acertar o heap*/
   (*n) = (*n)-1;	/*Acerta o valor de n*/
   DesceHeap(fl, *n);	/*Desce o primeiro elemento no heap de tamanho *n*/
   return x;
   
} /* Minimo */
   

Boolean AcrescentaLetra(char *cars, int *numCars, char letra, int maxCars) {
/* Acresenta � seq��ncia de caracteres 'cars' o caractere 'letra';
   incrementa 'numCars'. Devolve 'false' se o n�mero de caracteres
   ultrapassou 'maxcars'.  */
   
   if (*numCars == maxCars) return false; /*Se estorou a capacidade retorna false*/
   else
   {
      cars[*numCars] = letra; /*Acrescenta a letra em cars*/
      (*numCars)++;
      return true;
   }

} /* AcrescentaLetra */


Boolean AcrescentaBit(char *bits, int *numBits, short int t,int maxBits) {
/* Acresenta � seq��ncia de bits 'bits' o bit indicado por 't';
   incrementa 'numbits'. Devolve 'false' se o n�mero de bits
   ultrapassou 'maxBits'.  Esta fun��o seria muito mais complicada na
   pr�tica se fossem utilizados bits de verdade! */
	
   char c;
   
   if ((*numBits) == maxBits) return false; /*Se estorou a capacidade retorna false*/
   else
   {
      if (t==0) c = '0'; /*verifica se t cont�m 0 ou 1 e guarda o caracter '0' ou '1' em c.*/
      else c = '1';
      
      bits[*numBits] = c;
      (*numBits)++;
      return true;
   }
      
} /* AcrescentaBit */


void ImprimeArvoreAux(ArvHuf p, int level, char ar) { 
  
  int i;
	
  if (p!=NULL) {
    ImprimeArvoreAux(p->dir,level+1,'/');
    for (i=0;i<level-1;i++)
      printf("     ");
    if (level>0) 
      printf("  %c",ar);
    printf("%4d",p->peso);
    if ((p->esq)==NULL)                /* folha */
      printf(":%c",p->letra);
    printf("\n");  
    ImprimeArvoreAux(p->esq,level+1,'\\');
  }  

} /* ImprimeArvoreAux */

void LiberaArvoreAux(ArvHuf p){
/* Libera a mem�ria din�mica ocupada pela �rvore 'p'. */

    if (p!=NULL) /*Esse � o m�todo padr�o para libera��o de mem�ria din�mica*/
    {
        LiberaArvoreAux(p->esq);
        LiberaArvoreAux(p->dir);
        free(p);
    }
  
} /* LiberaArvoreAux */

void Inverte(int *SeqBits, int a){
/*Inverte a cadeia SeqBits com a elementos*/

	int aux, g=0;
	
	
	
	while (g<a) /*Esse while faz a invers�o*/
		{
			aux = SeqBits[g];
			SeqBits[g] = SeqBits[a-1];
			SeqBits[a-1] = aux;
			g++;
			a--;
		}
}
                    
                     
/* --------------------------------------------------------- */
/* Fun��es da interface                                      */
/* --------------------------------------------------------- */
                      
Boolean ConstroiHuffman(int freq[], int n) {
/* A partir das 'n' primeiras letras (2<=n<=26) come�ando com a letra
   'a', constr�i a �rvore de Huffman para compress�o de texto e guarda
   numa vari�vel local do m�dulo 'huffman.c'.  Numa outra vari�vel
   local guarda um vetor de apontadores para as folhas da �rvore
   (letras). Devolve 'true' se a constru��o teve sucesso; 'false' caso
   contr�rio. */

  ArvHuf floresta[SIZE_AMOSTRAL_SPACE];  /* Constituir� a fila de prioridade */
  ArvHuf m1, m2;
  int k=0;
  int i=n; /*variavel q vai servir de ref para colocar apontadores NULL em Folhas */
  char car = 'a';
  
    
  while (k<n)					/*Esse while controi a floresta 		*/
  {						/*q ser� transformada num heap posteriormente.	*/
      floresta[k] = CriaFolha(car+k, freq[k]);	/*Tb � contruido o vetor de apontadores para	*/
      if (floresta[k] == NULL ) return false;	/*as folhas (Folhas).				*/
      Folhas[k] = floresta[k];
      k++;
  }
  
  ConstroiHeap(floresta, n);	/*Constroi o heap*/
  
    
  while (n>1)  					/*Esse while � que cria a arvore de huffman,  */
  {						/*combinando as arvores at� sobrar um elemento*/
      m1 = Minimo(floresta, &n);		/*no heap, q � a arvore de huffman	      */
      m2 = Minimo(floresta, &n);
      floresta[n] = CombinaArvs(m1, m2);
      n++;
      SobeHeap(floresta, n-1);
  }
  
  
  
  while (i<TamanhoMaxAlfabeto) /*Esse while coloca apontadores		*/
  {                            /*nulos no final do vetor Folhas para	*/
      Folhas[i] = NULL;        /*detec��o de cars inv�lidos   		*/
      i++;
  }
  
  floresta[0]->pai = NULL;   /*O pai da raiz da arvore � NULL*/
  Arvore = floresta[0];  /*Floresta[0] cont�m a arvore de huffman.*/
    
  return true; /*Se deu tudo certo deve retornar true*/
  
} /* ConstroiHuffman */

void LiberaHuffman() {
/* Libera a mem�ria din�mica ocupada pelas estruturas criadas por
   'ConstroiHuffman'. */

  LiberaArvoreAux(Arvore);

} /* LiberaHuffman */


Boolean Comprime(char *cars, char *bits, int *numBits, int numBitsMax) {
/* Comprime a cadeia apontada por 'cars' (que termina com '\0') usando
   as estruturas j� constru�das, e deixa o resultado como uma
   seq��ncia de caracteres '0' e '1', simulando bits, na �rea apontada
   por 'bits'. Devolve em 'numBits' o n�mero total de bits gerado. Em
   caso de sucesso devolve 'true'; se aparecer um caractere inv�lido,
   ou se houver mais de 'numBitsMax' bits, devolve 'false'. */

	int i, k=0, x;
	ArvHuf p;
	int SeqBits[20]; /*Vai armazenar a cadeia de Bits do caracter q � buscado na arvore*/
	
	(*numBits)=0; /*numBits come�a com 0*/
	
	
	while (cars[k] != '\0') /*Para cada letra em cars, vai pegando a cadeia de bits correspondente*/
	{			/*na arvore de huffman, invertendo e colocando em *bits*/
		i=0;
		
		p = Folhas[(cars[k]) - 'a'];
		
		if (p==NULL) return false; /* � um caracter Inv�lido*/
		
		while (p->pai != NULL)		/*Esse while percorre a arvore de	*/
		{				/*huffman da folha at� a raiz,		*/
			SeqBits[i] = p->filho;	/*pegando os bits em p->filho		*/
			p = p->pai;
			i++;
				
		}
		
		
		Inverte(SeqBits, i);  /*Eu criei essa fun��o para inverter a cadeia de bits*/
		
		
		for (x=0; x<=i-1; x++) /*Esse for insere em bits os bits relativos a car[k]*/
		{
			if (!(AcrescentaBit(bits, numBits, SeqBits[x], numBitsMax))) return false; /*Encontrou algum erro na inser��o*/
		}
		
		k++; /*Incrementa k para para avan�ar para a pr�xima letra em cars*/
	}
		
	return true; /*Se chegou at� aqui quer dizer q deu certo a compacta��o*/
	
	
  
} /* Comprime */

   
Boolean Descomprime(char *cars, char *bits, int numBits, int numMaxCars) {
/* Descomprime a cadeia de pseudo-bits apontada por 'bits', de
   comprimento 'numBits' seguindo a �rvore de Huffman j� constru�da.
   Coloca no fim da cadeia descomprimida o terminador '\0'. Em caso de
   sucesso devolve 'true'; se aparecer uma codifica��o incompat�vel
   com a �rvore, ou se houver mais caracteres que 'numMaxCars' devolve
   'false'.*/

	ArvHuf p = Arvore; /*Vamos percorrer a arvore da ra�z at� as folhas atrav�s dessa variavel*/
	int k=0;  /*Guarda a posi��o do bit q t� sendo processado em bits*/
	int numCars=0; /*Guarda o n�mero de caracteres descomprimidos*/
	char c;
	
	
	while (k < numBits) 		/*Esse while verifica para cada bit em *bits se p � ou n�o folha */
	{				/*e toma as devidas providencias				 */	
		c = bits[k];
		if (c == '0') p = p->esq; /*Se c for 0 ent�o p deve seguir para a esquerda*/
		else p = p->dir;
		
		if ((p->esq == NULL) && (p->dir == NULL)) /*Se for uma folha acrescenta a letra em cars*/
		{
			if (!AcrescentaLetra(cars, &numCars, p->letra, numMaxCars)) return false; /*Deu erro*/
			p = Arvore; /*Se chegou numa folha p deve apontar para a raiz, para descer novamente*/
		}
		
		k++;
	}
	
	if (numCars == numMaxCars) return false; /*Verifica se existe caracteres suficientes para adicionar '\0'*/
	else cars[numCars++] = '\0';
	
	return true; /*Se chegou at� aqui teve sucesso...... Valeu...............*/	
  
} /* Descomprime */

/* --------------------------------------------------------- */
/* Fun��es auxiliares para os testes pelo programa principal */
/* --------------------------------------------------------- */

void ImprimeArvore() {
/* Imprime a �rvore de Huffman num formato leg�vel */

  ImprimeArvoreAux(Arvore,0,'/');
  

}/* ImprimeArvore */
